﻿using System;
using System.Collections.Generic;
using System.Text;


public class HuffManTreeDemo
{
    public static void Test()
    {
        int[] arr = { 13, 7, 8, 3, 29, 6, 1 };
        HuffmanTreeNode root = CreateHuffmanTree(arr);
        root.PreOrder();
    }

    public static HuffmanTreeNode CreateHuffmanTree(int[] arr)
    {
        List<HuffmanTreeNode> nodes = new List<HuffmanTreeNode>();
        for (int i = 0; i < arr.Length; i++)
        {
            nodes.Add(new HuffmanTreeNode(arr[i]));
        }

        while (nodes.Count > 1)
        {
            //排序 小-大
            nodes.Sort();
            //取出前两个权值最小的两颗二叉树
            HuffmanTreeNode left = nodes[0];
            HuffmanTreeNode right = nodes[1];

            // 构建新的二叉树
            HuffmanTreeNode parent = new HuffmanTreeNode(left.value + right.value);
            parent.left = left;
            parent.right = right;
            //从 list 中删除处理过的二叉树
            nodes.Remove(left);
            nodes.Remove(right);
            nodes.Add(parent);
        }

        // 返回赫夫曼树的root节点
        return nodes[0];
    }
}

